//
// Created by weslywang on 2020/6/27.
//
#include "../common/common.h"

bool isDebug = true;

bool isPalindrome(string str) {
    if (str.size() < 1) {
        return false;
    }
    for (int i = 0, k = str.size() - 1; i < k; i++, k--) {
        if (str[i] != str[k]) {
            return false;
        }
    }
    return true;
}

void dfs(string &str, vector<vector<int> > &list, vector<string> &row, int pos, vector<vector<string>> &result) {
    for (int i = pos + 1; i < list.size(); i++) {
        if (list[pos][i] == 1) {
            if (i == list.size() - 1) {
                vector<string> ans(row);
                ans.push_back(str.substr(pos, i - pos));
                result.push_back(ans);
            } else {
                row.push_back(str.substr(pos, i - pos));
                dfs(str, list, row, i, result);
                row.pop_back();
            }
        }
    }
}

vector<vector<string>> partition(string s) {
    int numRows = s.length() + 1;
    vector<vector<string>> result;
    vector<vector<int>> store(numRows);
    for (int i = 0; i < numRows; i++) {
        store[i].resize(numRows);
    }
    for (int i = 0; i < store.size(); i++) {
        for (int k = i + 1; k < store[i].size(); k++) {
            string str = s.substr(i, k - i);
            if (isPalindrome(str)) {
                store[i][k] = 1;
                if (isDebug) {
                    cout << "[" << i << "," << k << "] " << str << " true" << endl;
                }
            } else {
                store[i][k] = 0;
                if (isDebug) {
                    cout << "[" << i << "," << k << "] " << str << " false" << endl;
                }
            }
        }
    }

    vector<string> row;
    dfs(s, store, row, 0, result);

    if (isDebug) {
        Common common;
        common.printVector(store);
    }
    return result;
}

int main() {
    struct timeval start;
    struct timeval end;
    unsigned long timer;
    Common common;
    int a[] = {1, 2, 3, 4, 5};

    vector<string> inputList = common.loadStringData2();
    for (int i = 0; i < inputList.size(); i++) {
        gettimeofday(&start, NULL);
        vector<vector<string>> re = partition(inputList[i]);
        cout << "结果：" << endl;
        common.printVector(re);
        gettimeofday(&end, NULL);
        timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
        cout << timer / 1000 << "毫秒" << endl;
        cout << "**************" << endl;
    }
    return 0;
}